package com.cfw.sparsearray;

public class SparseArray {

	public static void main(String[] args){
		
		
		/**
		 * 保存五子棋 数据，每一步骤使用稀疏数组表示,棋盘的X和Y 是11
		 */
		
		
		//思路
		/**
		 * 1 遍历 棋盘origin，获取非默认的值个数 num
		 * 2 创建 一个二维数组，长度为 sparseArray[num+1][3]
		 * 3 将棋盘的x，y，num 保存到 sparseArray 第一行
		 * 4. 遍历origin ，按照顺序，将 非默认数值的元素，填入sparseArray，
		 * 每一行元素分别为其x，y，和值
		 * 
		 * 稀疏数组恢复成源数组
		 *1. 获取x = sparseArray[0][0] 和 y =sparseArray[1] 创建一个 数组 array[x][y]
		 * 2. 遍历sparseArray ，第二行开始，获取 第一个元素 x1，第一个元素y2，和值z
		 * 分别赋值给 array[x1][y1]= z 
		 * 
		 * 3.完成
		 *
		 */
		
		
		//
		
		int origin [][] = new int[11][11];
		
		//设置棋盘的落子，1代表黑骑，2 代表白旗
		
		origin[1][2] =1;
		origin[2][3] =2;
		
		
		//生成稀疏数组
		
		//打印并获取有效值个数
		int num = 0;
		
		for (int i = 0; i < origin.length; i++) {
			
			for (int j = 0; j < origin[i].length; j++) {
				if (origin[i][j]!=0) {
					num++;
				}
				System.out.printf("%d\t",origin[i][j]);
			}
			System.out.println("");
		}
		
		
		int sparseArray [][] = new int[num+1][3];
		
		sparseArray[0][0] =11;
		sparseArray[0][1]=11;
		sparseArray[0][2]=num;
		
		//设置稀疏数组有效值 ，
		int count =0;
		for (int i = 0; i < origin.length; i++) {
			for (int j = 0; j < origin[i].length; j++) {
				if (origin[i][j]!=0) {
					count++;
					sparseArray[count][0] =i;
					sparseArray[count][1]=j;
					sparseArray[count][2]=origin[i][j];
				}
			}
		}
		
		//打印数组数组
		
		for (int i = 0; i < sparseArray.length; i++) {
			System.out.printf("%d\t%d\t%d\t\n",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
		}
		
		
		//将稀疏数组恢复成原始数组
		int originArray[][] = new int[sparseArray[0][0]][sparseArray[0][1]];
		
		//从第二行开始
		for (int i = 1; i < sparseArray.length; i++) {
			originArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
			
		}
		
		//打印原数组
		
		for (int i = 0; i < originArray.length; i++) {
			for (int j = 0; j < originArray[i].length; j++) {
					System.out.printf("%d\t",originArray[i][j]);
			}
			System.out.println("");
		}

		
				
		
		
		
	}

}
 